package com.foxzzz.greedy;


public class Solution134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            int index = i;
            int sumGas = gas[index];

            while ((sumGas = sumGas - cost[index]) >= 0) {
                index = (index + 1) % gas.length;
                sumGas += gas[index];
                if (index % gas.length == i) {
                    return i;
                }
            }

        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution134().canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
        System.out.println(new Solution134().canCompleteCircuit(new int[]{ 2, 3, 4}, new int[]{3, 4, 3}));
    }
}
